/**
 * 
 */
package datamodel.huffman.tree;

import java.util.ArrayList;
import java.util.Vector;

import datamodel.RGB;


/**
 * A implementation of your Huffman tree.<br>
 * 
 * @author Kevin Munk, Jakob Karolus
 * @version 1.0
 * 
 */
public class Tree {
	/**
	 * Node class
	 * (If a Tree contained RGB objects directly, empty nodes would have to be represented as RGBs.
	 * A empty node however is not a color. Null can't be used, because it forbids traversal.)
	 * static: No Tree instance needed for usage
	 */
	public static class Node {
		private RGB rgb = null;
		public Node(RGB rgb) {
			setRGB(rgb);
		}
		public void setRGB(RGB rgb) {
			this.rgb = rgb;
		}
		public RGB getRGB() {
			return rgb;
		}
		public boolean hasRGB(){
			return rgb != null;
		}
		
		/* Trees may be stored in hash maps. HashMap.containsKey() uses Tree.hashCode().
		 * Tree contains vector of Nodes. -> Node needs hashCode() too.
		 * (non-Javadoc)
		 * @see java.lang.Object#hashCode()
		 */
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + ((rgb == null) ? 0 : rgb.hashCode());
			return result;
		}
		
		@Override
		public boolean equals(Object o) {
			if(! (o instanceof Node)) // catches also o == null
				return false;
			Node n = (Node)o;
			if(rgb == null && n.rgb == null)
				return true;
			else if(rgb == null || n.rgb == null) // only one is null; or else we would have returned earlier
				return false;
			return rgb.equals(n.rgb);
		}
	}
	

	//TODO: add attributes and methods for your implementation
	
	private Vector<Node> tree = new Vector<Node>();
	private int currentPosition = 0;
	
	/**
	 * Moves to the left child of the current node
	 * @return True if successful
	 */
	public boolean moveToLeftNode() {
		if (this.hasLeftNode()){
			this.currentPosition = this.getLeftChildPosition();
			return true;
		}
		return false;
	}

	/**
	 * Moves to the right child of the current node
	 * @return True if successful
	 */
	public boolean moveToRightNode() {
		if(this.hasRightNode()){
			this.currentPosition = this.getRightChildPosition();
			return true;
		}
		return false;
	}

	/**
	 * Moves to the parent of the current node
	 * @return True if successful
	 */
	public boolean moveToParentNode() {
		if (this.hasParentNode()){
			this.currentPosition = this.getParentPosition();
			return true;
		}
		return false;
	}

	/**
	 * Checks for a left child
	 * @return True if l.c. exists
	 */
	public boolean hasLeftNode() {
		int lcPos = this.getLeftChildPosition();
		if(lcPos < 0 || lcPos >= this.tree.size()){
			return false;
		} else if (this.tree.get(lcPos) != null){
			return true;
		}
		return false;
	}

	/**
	 * Checks for right child
	 * @return True if it exists
	 */
	public boolean hasRightNode() {
		int rcPos = this.getRightChildPosition();
		if (rcPos < 0 || rcPos >= this.tree.size()){
			return false;
		} else if (this.tree.get(rcPos) != null){
			return true;
		}
		return false;
	}

	/**
	 * Checks for parent node
	 * @return True if it exists
	 */
	public boolean hasParentNode() {
		int parentPos = this.getParentPosition();
		if (parentPos < 0 || parentPos >= this.tree.size()){
			return false;
		} else if (this.tree.get(parentPos) != null){
			return true;
		}
		return false;
	}

	/**
	 * Sets a left child
	 * @param node The child
	 * @return True on success
	 */
	public boolean setLeftNode(Node node) {
		return this.setNodeAt(this.getLeftChildPosition(), node);
	}

	/**
	 * Sets a right child
	 * @param node The child
	 * @return True on success
	 */
	public boolean setRightNode(Node node) {
		return this.setNodeAt(this.getRightChildPosition(), node);
	}

	/**
	 * Sets a node at the current position
	 * @param node The node
	 * @return True on success
	 */
	public void setCurrentNode(Node node) {
		if(this.tree.size() == 0){
			this.tree.add(node);
			currentPosition = 0;
		} else {
			this.setNodeAt(this.currentPosition, node);
		}
	}

	/**
	 * Returns current node
	 * @return the node
	 */
	public Node getCurrentNode() {
		if (this.tree.size() == 0){
			return null;
		}
		return this.tree.get(currentPosition);
	}

	/**
	 * Moves to root
	 * @return True if successful
	 */
	public boolean moveToRoot() {
		if ((this.tree.size() >= 1) && (tree.get(0) != null)){
			this.currentPosition = 0;
			return true;
		}
		return false;
	}

	/**
	 * Deletes the tree
	 */
	public void clearTree() {
		this.tree.clear();
		this.currentPosition = 0;
		
	}
	
	/**
	 * Sets a given TreeNode node at the given position pos in this SequentialTree
	 * @param pos
	 * @param node
	 * @return true if successful, false otherwise (no root set)
	 */
	private boolean setNodeAt(int pos, Node node){
		// If the tree is not empty and there exists a root
		if ((this.tree.size() >= 1) && (this.tree.get(0) != null)){
			if (pos < this.tree.size()){
				this.tree.setElementAt(node, pos);
			} else {
				final int TREE_SIZE = this.tree.size();
				for (int i = 0; i < pos - TREE_SIZE; i++){
//					this.tree.add(null);
					// insert Nodes with null as RGB
					this.tree.add(new Node(null));
				}
				this.tree.add(node);
			}
			return true;
		}
		return false;
	}
	
	/**
	 * Determines the index of the right child of the current node
	 * @return the index of the right child of the current node
	 */
	private int getRightChildPosition(){
		return 2 * (this.currentPosition + 1);
	}
	
	/**
	 * Determines the index of the left child of the current node
	 * @return the index of the left child of the current node
	 */
	private int getLeftChildPosition(){
		return (2 * (this.currentPosition + 1)) - 1;
	}
	
	/**
	 * Determines the index of the parent of the current node
	 * @return the index of the parent of the current node
	 */
	private int getParentPosition(){
		return ((this.currentPosition + 1) / 2) - 1;
	}

	/* Needed for storage in map. containsKey() doesn't use equals() but hashCode().
	 * (non-Javadoc)
	 * @see java.lang.Object#hashCode()
	 */
	/**
	 * Needed for storage in hash-based containers.
	 */
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		// tree.hashCode() calls hashCode() on Nodes contained in vector. -> implement hashCode() in Node
		result = prime * result + ((tree == null) ? 0 : tree.hashCode());
		return result;
	}

	/**
	 * Compares two trees
	 * @param t other tree
	 * @return true if equal
	 */
	public boolean equals(Tree t){
		boolean thisResult = false;
		boolean leftResult = false;
		boolean rightResult = false;
		if (this.getCurrentNode().equals(t.getCurrentNode())){
			thisResult = true; 
		}
		if ((! t.hasLeftNode()) && (! this.hasLeftNode())) {
			if ((! t.hasRightNode()) && (! this.hasRightNode())){
				return thisResult;
			} else if((t.hasRightNode()) && (this.hasRightNode())){				
				this.moveToRightNode();
				t.moveToRightNode();
				rightResult = this.equals(t);
				this.moveToParentNode();
				t.moveToParentNode();
				
				
				return thisResult && rightResult;
				
			}
		} else if(t.hasLeftNode() && this.hasLeftNode()) {
			if ((! t.hasRightNode()) && (! this.hasRightNode())){
				this.moveToLeftNode();
				t.moveToLeftNode();
				leftResult = this.equals(t);
				this.moveToParentNode();
				t.moveToParentNode();
				return thisResult && leftResult;
			} else if((t.hasRightNode()) && (this.hasRightNode())){
				this.moveToLeftNode();
				t.moveToLeftNode();
				leftResult = this.equals(t);
				this.moveToParentNode();
				t.moveToParentNode();
				
				this.moveToRightNode();
				t.moveToRightNode();
				rightResult = this.equals(t);
				this.moveToParentNode();
				t.moveToParentNode();
				
				return thisResult && leftResult && rightResult;
			}
		}
		return false;
	}
	
	/**
	 * Compares two trees
	 */
	public boolean equals(Object o){
		if (o instanceof Tree){
			this.moveToRoot();
			((Tree) o).moveToRoot();
			return this.equals((Tree) o);
		} else {
			return false;
		}
	}
	/**
	 * Returns tree size
	 * @return the size
	 */
	public int treeSize(){
		return tree.size();
	}
	
	/**
	 * Removes the lowest tree level (for compression). Sets current position to root to guarantee valid object state
	 * @return a list of the deleted nodes
	 */
	public ArrayList<RGB> removeLowestTreeLevel(){
		ArrayList<RGB> cutOff = prepareForCompression();
		// Determine position until which the old tree should be copied (remove padding nodes from
		// resulting tree in last row)
		int until = 0;
		for(int i=0; i<getTreeHeight()-1; ++i) {
			until += Math.pow(2, i);
		}
		--until;
		
		while(!tree.get(until).hasRGB() && until != 0)
			--until;
		
		Vector<Node> reducedTree = new Vector<Node>();
		
		for(int i=0; i<=until; ++i)
			reducedTree.add(tree.get(i));
		
		tree = reducedTree;
		moveToRoot(); // guarantee usable object
		return cutOff;
	}

	/**
	 * Prepares tree for compression
	 * @return
	 */
	private ArrayList<RGB> prepareForCompression(){
		// Determine index of first element in last row.
		int from=0;
		for(int i=0; i<getTreeHeight()-1; ++i) {
			from += Math.pow(2, i);
		}
		
		// Save RGBs that will be cut off.
		ArrayList<RGB> cutOffList = new ArrayList<RGB>();
		
		// Iterate over Nodes in last row. If Node contains color, set its parent to white color.
		for(int i=from; i<treeSize(); ++i) {
			if(tree.get(i).hasRGB()) {
				cutOffList.add(tree.get(i).getRGB());
				int parent = (i + 1) / 2 - 1; // Formula stolen from getParentPosition().
				tree.get(parent).setRGB(new RGB(255,255,255,255));
			}
		}
		
		return cutOffList;
	}
	
	/**
	 * Returns the height of the tree
	 * @return tree height
	 */
	public int getTreeHeight() {
		int currentPosBackup = currentPosition;
		moveToRoot();
		int res = getTHHelper(1);
		currentPosition = currentPosBackup;
		return res;
	}
	
	
	private int getTHHelper(int k) {
		if(!moveToLeftNode())
			return k;
		return getTHHelper(k+1);
	}

}
